package com.sicheng.lc.周赛.分类.栈.单调栈or单调队列;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/9 10:02
 */
public class 子数组范围和 {
    //https://leetcode.cn/problems/sum-of-subarray-ranges/
    // 计算贡献值 每个元素作为最大值或者最小值出现在多少子数组中
    // 以nums[i] 为中心 ，找到左右边最远处，以nums[i]最大值
    // 以nums[i] 为中心 ，找到左右边最远处，以nums[i]最小值
    // (右边等于nums[i]的纳入,左边不行，因为左边等于nums[i]的已经向右扩散过)
    // 产生的连续子数组且包含nums[i]的总个数  (i-l+1)*(r-i+1)

    // 以最大值举例说明  拆分需要连续且包含nums[i]
    // 数组假设 元素3 的索引是100
    // ...5 0 2 3 1 2 4....
    //  扩散后 l=98, r=102
    //  向左边扩散得到的最长数组 {0,2,3} 拆分===> {3},{2,3},{0,2,3}
    //  向右边扩散得到的最长数组 {3,1,2} 拆分===> {3},{3,1},{3,1,2}
    //  左边,右边里选择一个拆分后的子数组进行拼接组合,拼接的过程逻辑上左右重合的nums[i]只算一次
    //  {2,3}+{3,1,2}==>{2,3,1,2} ，{3}+{3}==>{3} ,{2,3}+{3,1}==>{2,1}.... 共 3 * 3 = 9个子数组
    //  排列组合计数问题:(i-l+1) * (r-i+1)


    // 1.逆向思维在里面,以nums[i]为最值找边界，此题还是比较难想的
    // 2.扩散时向左不纳入等于nums[i]的,向右纳入
    // 3.就是组合计数，这也是一个难点
    // 4.就是贡献值 最大值的贡献是nums[i],最小值的贡献是-nums[i]
    static long res;

    public long subArrayRanges(int[] nums) {
        res = 0;
        for (int i = 0; i < nums.length; i++) {
            int l = i, r = i;
            while (l > 0 && nums[i] > nums[l - 1]) l--;
            while (r + 1 < nums.length && nums[i] >= nums[r + 1]) r++;

            res += (long) (i - l + 1) * (r - i + 1) * nums[i];
            l = i;
            r = i;
            while (l > 0 && nums[i] < nums[l - 1]) l--;
            while (r + 1 < nums.length && nums[i] <= nums[r + 1]) r++;
            res -= (long) (i - l + 1) * (r - i + 1) * nums[i];
        }

        return res;
    }
}
